The present invention relates to an image feature extractor for extracting image features of a pattern image such as a skin pattern image represented by a fingerprint or a palm-print, an image feature analyzer for analyzing the image features, and an image matching system for collating the pattern image with those filed in a database.
In the following description, the present invention is explained in connection with a skin pattern feature extractor, a skin pattern feature analyzer and a skin pattern matching system applied to personal identification as representation examples of the above devices. However, it will be easily understood that the present invention can be widely applied to matching verification of pattern images having certain features, without limited to the skin pattern matching verification.
As a most orthodox art for identifying a skin pattern such as a fingerprint or a palm-print, there is known a matching verification method making use of feature points of the fingerprint called the minutia matching which is disclosed in a Japanese Patent entitled "Fingerprint Collation System" published as a specification No. 63-34508. However, a problem of the minutia matching is that it takes a lot of computational time because of a large amount of data to be processed.
For alleviating the problem, there is proposed a technique for reducing a number of candidates to be verified by way of the Ten Print Card, which is disclosed in "Fingerprint Card Classification for Identification with a Large-Size Database" by Uchida, et al., Technical Report of IEICE (The Institute of Electronics, Information and Communication Engineers) PRU95-201 (January 1996). In the Fingerprint Classification of this technique, a high-speed rough matching is performed referring to certain features such as the basic fingerprint classification category, distances between singular points, namely, cores or deltas, etc., for pre-selecting candidates to be verified with the minutia matching. As the basic fingerprint classification categories, a fingerprint pattern of each finger is classified into one of basic classification categories, such as the Whorl, the Right Loop, the Left Loop or the Arch, and numbers of ridge lines and the distances between cores and deltas of each finger are extracted as other features together with their confidence values, for the rough matching of the technique.
Data amount of these features is at most several hundred bytes for a card, far smaller than the several thousand bytes necessary for the minutia matching. The smaller data amount, and consequently the smaller calculation amount, enable a high-speed fingerprint verification.
Thus, by reducing number of candidates before the minutia matching, the pre-selection technique of the prior document by Uchida et al. enables to improve total cost performance of the fingerprint verification system as a whole.
However, because the deltas are usually found in edge parts of the fingerprint, the numbers of ridge lines and the distances between a core and a delta are often difficult to be extracted when a so called roll printing is not performed correctly. The roll printing means here to take the fingerprint pattern by pressing a fingertip rolling on a card, as usually performed when the police take the fingerprint. Furthermore, the above technique is not efficient to pre-select the Arch patterns which have no delta.
Therefore, methods for improving pre-selection performance have been sought. One promising solution is to find other appropriate features to be used for the rough matching in place of or in addition to the above features. One of the possible features is the direction pattern of fingerprint ridge lines. "Personal Verification System with High Tolerance of Poor Quality Fingerprints" by Sasagawa et al., the transactions of IEICE D-II, Vol. J72-D-II, No. 5, pp. 707-714, 1989, is an example of usage of the direction pattern to the rough matching.
Feature value having such many dimensions as the direction pattern of the fingerprint ridge lines, however, makes difficult the high-speed matching verification. Therefore, when applying such feature value, it is necessary to find a feature extraction method enabling to extract a condensed feature value thereof having an appropriate dimension size giving good results and sufficient efficiency at the same time. A well-known method of such a feature extraction is the principal component analysis. An example of the method applied to the direction pattern of the fingerprint ridge lines is described in a paper of C. L. Wilson et al., entitled "Massively Parallel Neural Network Fingerprint Classification System", NISTIR 4880, 1992, July, published by National Institute of Standards and Technology.
In the method of C. L. Wilson et al., the direction pattern is processed as follows.
First, training data of N fingerprint images are prepared. Then, defining feature vectors composed of ridge directions each representing local flow of ridge lines, the principal component analysis is performed for distribution of the feature vectors to obtain principal component vectors having larger eigenvalues. Using the principal component vectors thus obtained, Karhunen Loeve Transform (hereafter abbreviated as KLT) of the feature vector of an objective fingerprint image is performed, whereof feature values of upper dimensions are extracted as the condensed feature value.
In the following paragraphs, more details of the feature extraction using the KLT are described.
For the first, a variance-covariance matrix V is calculated as follows from feature vectors u.sub.i (i=1 to N) of the N fingerprint images prepared for the training. ##EQU1##
Here, the feature vectors u.sub.i are column vectors of M dimensions, u is a mean vector of u.sub.i, and the upper suffix.sup.t means a transpose.
Eigenvalues of the variance-covariance matrix V being represented by .lambda..sub.i (i=1, . . . , M; .lambda..sub.i &gt;.lambda..sub.i+1), eigenvectors corresponding to the eigenvalues .lambda..sub.i are represented by .psi..sub.i. These eigenvectors .psi..sub.i are the principal component vectors and one corresponding to a largest eigenvalue .lambda..sub.1 is called a first principal component vector, followed by a second, a third, . . . , a M-th principal component vector in the order of corresponding eigenvalue.
For a feature vector u of an objective fingerprint image, which is not used for the training, projection of the feature vector u to a partial space defined by one or more primary (corresponding to largest eigenvalues) principal component vectors .psi..sub.i is calculated, that is, projection components v.sub.i around the mean vector u are obtained as follows: EQU v.sub.i =.psi..sup.t.sub.i (u-u)
The projection components v.sub.i thus obtained are the feature values extracted by way of the KLT.
In C. L. Wilson et al., a feature vector composed, as its components, of primary projection components v.sub.i corresponding to the primary principal component vectors is input to a neural network for the fingerprint classification. However, these extracted feature values are used only for the classification and any application to the matching verification is not taught therein.
Although it is not applied to the skin pattern analysis, there is described an example of a facial image matching verification making use of feature values obtained by the KLT, in "Eigenfaces for Recognition" by A. Pentland et al., MIT Media Lab Vision and Modeling Group, Technical Report #154 and also in "Probabilistic Visual Learning for Object Detection" by B. Moghaddam and A. Pentland, pp. 786-793 of Proceedings of the 5-th International Conference on Computer Vision, 1995. In these two documents, a method of facial image matching verification is described, wherein a vector consisting of each pixel value of a facial image as each component thereof is used as the source feature vector, and the facial matching verification is performed according to Euclidean distance or Mahalanobis distance of the condensed feature vector extracted by way of the KLT of the source feature vector.
However, these prior arts have problems when applied to the fingerprint matching verification.
By Uchida et al., it is often difficult to extract sufficient features such as distances or numbers of ridge lines between the core and the delta when the rotation stamping is not performed correctly because the deltas are usually found in edge parts of the fingerprint. Furthermore, the Arch patterns having no delta cannot be pre-selected sufficiently.
In C. L. Wilson et al., there is a description concerning fingerprint feature extraction making use of the KLT applied to fingerprint classification, but no description concerning application thereof to the fingerprint matching verification used, for example, to pre-select the verification candidates, as intended in Uchida et al.
Although not to the fingerprint matching verification, application of the KLT to facial image matching verification is disclosed in the documents of A. Pentland et al. The fingerprint image may be processed according to Euclidean distances or Mahalanobis distances in the same way with the above method of A. Pentland et al. However, many of the available fingerprint images are of fairly low grade and sufficient reliability cannot be expected with such a simple method as that of A. Pentland et al., relying simply upon the condensed feature vector. The reason is that necessary consideration is not paid to confidence of the extracted features there.
It is the same with Uchida et al., wherein the distance between pattern images is defined with a feature value and a confidence value. However, the confidence value is calculated heuristically and there is given no logical evidence.
Therefore, a primary object of the present invention is to embody a matching verification architecture for efficiently collating pattern images such as skin patterns by resolving the above problems, and to provide an image feature extractor, an image feature analyzer and an image matching system, wherein a high-speed and a high-precision processing is realized.